#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

class topToEnd {
    int **dpTable;
public:
    int longestCommonSubsequence(string s1, string s2) {
        int length1 = s1.size();
        int length2 = s2.size();
        dpTable = new int* [length1];
        for (int i = 0; i < length1; i++) {
            dpTable[i] = new int[length2];
        }
        for (int i = 0; i < length1; i++) {
            for (int j = 0; j < length2; j++)
                dpTable[i][j] = -1;
        }
        return dp(s1, 0, s2, 0);
    }

    int dp(string& s1, int i, string& s2, int j) {
        if (i == s1.size() || j == s2.size())
            return 0;
        if (dpTable[i][j] != -1)
            return dpTable[i][j];
        if (s1[i] == s2[j])
            dpTable[i][j] = 1 + dp(s1, i + 1, s2, j + 1);
        else 
            dpTable[i][j] = max(dp(s1, i + 1, s2, j), dp(s1, i, s2, j + 1));
        return dpTable[i][j];
    }
};

class endToTop {
public:
    int longestCommonSubsequence(string s1, string s2) {
        int length1 = s1.size();
        int length2 = s2.size();
        int dpTable[length1 + 1][length2 + 1];
        for (int i = 0; i < length1; i++)
            dpTable[i][0] = 0;
        for (int i = 0; i < length2; i++)
            dpTable[0][i] = 0;

        for (int i = 1; i <= length1; i++) {
            for (int j = 1; j <= length2; j++) {
                if (s1[i - 1] == s2[j - 1])
                    dpTable[i][j] = 1 + dpTable[i - 1][j - 1];
                else
                    dpTable[i][j] = max(dpTable[i - 1][j], dpTable[i][j - 1]);
            }
        } 
        return dpTable[length1][length2];
    }
};

// 删除字符的最小数目：反向使用LCS
class usingMaxLCS {
public:
    int minDistance(string word1, string word2) {
        int maxlcs = maxLCS(word1, word2);
        return word1.size() - maxlcs + word2.size() - maxlcs;
    }

    int maxLCS(string s1, string s2) {
        int m = s1.size();
        int n = s2.size();
        int dpTable[m + 1][n + 1];

        for (int i = 0; i <= m; i++)
            dpTable[i][0] = 0;
        for (int i = 0; i <= n; i++)
            dpTable[0][i] = 0;
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1[i - 1] == s2[j - 1])
                    dpTable[i][j] = dpTable[i - 1][j - 1] + 1;
                else
                    dpTable[i][j] = max(dpTable[i - 1][j], dpTable[i][j - 1]);
            }
        }
        return dpTable[m][n];
    }
};

// 删除字符ascii码和的最小值
class directly {
public:
    int minimumDeleteSum(string s1, string s2) {
        int m = s1.size();
        int n = s2.size();
        int dpTable[m + 1][n + 1];
        dpTable[0][0] = 0;

        for (int i = 1; i <= m; i++)
            dpTable[i][0] = dpTable[i - 1][0] + s1[i - 1];
        for (int i = 1; i <= n; i++)
            dpTable[0][i] = dpTable[0][i - 1] + s2[i - 1];
        
        // 直接求最小值
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1[i - 1] == s2[j - 1])
                    dpTable[i][j] = dpTable[i - 1][j - 1];
                else 
                    dpTable[i][j] = min( (s1[i - 1] + dpTable[i - 1][j]), (s2[j - 1] + dpTable[i][j - 1]) );
            }
        }

        return dpTable[m][n];
    }
};

class usingLCS {
public:
    int minimumDeleteSum(string s1, string s2) {
        int m = s1.size();
        int n = s2.size();
        int dpTable[m + 1][n + 1];
        memset(dpTable, 0, sizeof(dpTable));

        for (int i = 1; i <= m; i++) {
            // 求LCS和最大
            for (int j = 1; j <= n; j++) {
                if (s1[i - 1] == s2[j - 1])
                    dpTable[i][j] = dpTable[i - 1][j - 1] + s1[i - 1];
                else 
                    dpTable[i][j] = max(dpTable[i - 1][j], dpTable[i][j - 1]);
            }
        }

        // 反向减去LCS和即为答案
        int ans = 0;
        for (int i = 0; i < m; i++) 
            ans += s1[i];
        for (int j = 0; j < n; j++)
            ans += s2[j];
        return ans - 2 * dpTable[m][n];
    }
};